package com.lun.swordtowardoffer2.c15;

import java.util.HashMap;
import java.util.HashSet;
import java.util.List;
import java.util.Map;
import java.util.Map.Entry;
import java.util.Set;

public class CalcEquation {

	public double[] calcEquation(List<List<String>> equations, double[] values, List<List<String>> queries) {
		
		Map<String, Map<String, Double>> graph = buildGraph(equations, values);
		double[] result = new double[queries.size()];
		Set<String>  visited = new HashSet<>();
		
		for(int i = 0; i < queries.size(); i++) {
			List<String> query = queries.get(i);
			
			String a = query.get(0), b = query.get(1);
			
			if(!graph.containsKey(a) || !graph.containsKey(b)) {
				result[i] = -1.0;
			}else {
				visited.clear();
				result[i] = dfs(graph, visited, a, b);
			}
			
		}
		
		return result;
	}
	
	private double dfs(Map<String, Map<String, Double>> graph, Set<String> visited,// 
			 String start, String end) {
		
		if(start.equals(end)) {
			return 1.0;
		}
		
		visited.add(start);
		for(Entry<String, Double> entry : graph.get(start).entrySet()) {
			String key = entry.getKey();
			if(!visited.contains(key)) {
				double next = dfs(graph, visited, key, end);
				if(next > 0) {
					return entry.getValue() * next;
				}
			}
			
		}
		visited.remove(start);
		return -1.0;
		
	}

	private Map<String, Map<String, Double>> buildGraph(List<List<String>> equations, double[] values) {
		Map<String, Map<String, Double>> result = new HashMap<>();
		
		for(int i = 0; i < values.length; i++) {
			List<String> equation = equations.get(i);
			String a = equation.get(0), b = equation.get(1);
			put(a, b, values[i], result);
			put(b, a, 1 / values[i], result);
		}
		
		return result;
	}

	private void put(String a, String b, double value, Map<String, Map<String, Double>> result){
		if(result.containsKey(a)) {
			result.get(a).put(b, value);
		}else {
			Map<String, Double> newMap = new HashMap<>();
			newMap.put(b, value);
			result.put(a, newMap);
		}
		
		//书中简洁的方法
//		result.putIfAbsent(a, new HashMap<>());
//		result.get(a).put(b, value);
	}
	
}
